1. Field
Embodiments relate to a method and apparatus to plan a motion path of a robot, which is not obstructed by an obstacle in a working environment.
2. Description of the Related Art
In general, a mechanical device which performs motions similar to human motion using an electrical or magnetic mechanism is called a robot. Early robots included manipulators used for automated or unmanned tasks of manufacturing plants or industrial robots such as transportation robots, and performed dangerous tasks, simply repeated tasks or tasks using large force in place of a human. Recently, research into a humanoid robot which has joints similar to those of a human, coexists with a human in a working and living space of the human and provides various services has been actively conducted.
Such a humanoid robot performs tasks using a manipulator which may move similarly to the arm or hand motion of a human by an electrical or mechanical mechanism. In most manipulators which are currently being used, several links are connected to each other. A connection portion between the links is called a joint. The motion characteristics of the manipulator are determined according to a geometrical relationship. Mathematical representation of such a geometrical relationship is called kinematics. In general, the manipulator moves an end effector of a robot with such kinematic characteristics in a direction (goal point) to perform a task.
In order to allow the manipulator to perform a given task (e.g., grasp an object), it is important to generate a motion path from an initial position (start point) before the manipulator performs a task to a final position (goal point) where the task may be performed, that is, an object may be grasped. The path in which the manipulator may move from the start point to the goal point without colliding with an obstacle within a working area is automatically generated by an algorithm. The method of generating the path is divided into a process of searching for a free space which does not cause collision with an obstacle and a process of planning the motion path of the manipulator in the free space.
Hereinafter, in a sampling-based path planning algorithm which plans an optimal path to connect given start and goal points while satisfying constraints, such as obstacle avoidance, a method of using a Rapidly-exploring Random Tree (RRT) algorithm in a situation with a high degree of freedom or complicated constraints will be described.
The RRT algorithm is a method of repeating a process of selecting a closest node from an initial start point using a randomly sampled configuration in a Configuration Space (C-Space), in which the manipulator performs a task, so as to expand a tree, and searching for a motion path to a goal point. A node having a smallest goal score is selected from the tree using a goal function composed of a function of a distance from the goal point to an end-effector and a directional vector so as to expand the tree.
However, in the RRT algorithm of the related art, if a goal function is not accurately determined when the closest node is selected so as to expand the tree reaching the goal point, local minima occur and thus a solution may not be obtained. In addition, it takes considerable time to expand the tree. Even when escaping from local minima, the tree may be expanded in a wrong direction until local minima are recognized. Therefore, a speed to search for the solution may be decreased and thus a time consumed to search for a path may be increased.